home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 11 / Cream of the Crop 11-2.iso / os2 / rsynth1.zip / trie.c < prev    next >
C/C++ Source or Header  |  1994-11-08  |  1KB  |  81 lines
  1. #include <config.h>
  2. /* $Id: trie.c,v 1.13 1994/11/08 13:30:50 a904209 Exp a904209 $
  3.  */
  4. char *trie_id = "$Id: trie.c,v 1.13 1994/11/08 13:30:50 a904209 Exp a904209 $";
  5. #include <useconfig.h>
  6. #include <stdio.h>
  7. #include "proto.h"
  8. #include "trie.h"
  9.  
  10. struct trie_s
  11.  {
  12.   struct trie_s *otherwise;
  13.   struct trie_s *more;
  14.   void *value;
  15.   char ch;
  16.  };
  17.  
  18. void
  19. trie_insert(r, s, value)
  20. trie_ptr *r;
  21. char *s;
  22. void *value;
  23. {
  24.  trie_ptr p = NULL;
  25.  char ch;
  26.  while ((ch = *s++))
  27.   {
  28.    while ((p = *r))
  29.     {
  30.      if (p->ch == ch)
  31.       break;
  32.      else
  33.       r = &p->otherwise;
  34.     }
  35.    if (!p)
  36.     {
  37.      p = (trie_ptr) malloc(sizeof(*p));
  38.      memset(p, 0, sizeof(*p));
  39.      p->ch = ch;
  40.      *r = p;
  41.     }
  42.    r = &p->more;
  43.   }
  44.  p->value = value;
  45. }
  46.  
  47. void *
  48. trie_lookup(r, sp)
  49. trie_ptr *r;
  50. char **sp;
  51. {
  52.  char *s = *sp;
  53.  char *value = NULL;
  54.  char ch;
  55.  while ((ch = *s))
  56.   {
  57.    trie_ptr *l = r;
  58.    trie_ptr p;
  59.    while ((p = *l))
  60.     {
  61.      if (p->ch == ch)
  62.       break;
  63.      else
  64.       l = &p->otherwise;
  65.     }
  66.    if (p)
  67.     {
  68.      *l = p->otherwise;
  69.      p->otherwise = *r;
  70.      *r = p;
  71.      r = &p->more;
  72.      value = (char *) p->value;
  73.      s++;
  74.     }
  75.    else
  76.     break;
  77.   }
  78.  *sp = s;
  79.  return value;
  80. }
  81.